/* 二叉树中序遍历 */
const tree = {
    val: "a",
    left: {
        val: "b",
        left: {
            val: "e",
            left: null,
            right: null,
        },
        right: {
            val: "f",
            left: null,
            right: null,
        },
    },
    right: {
        val: "c",
        left: {
            val: "g",
            left: null,
            right: null,
        },
        right: {
            val: "h",
            left: null,
            right: null,
        },
    },
};

/* 递归版 */
/* const inOrder = (root) => {
  if (!root) return;
  inOrder(root.left);
  console.log(root.val);
  inOrder(root.right);
}; */

/* 非递归版 */
const inOrder = (root) => {
    const stack = [root];
    let p = root;
    while (stack.length || p) {
        while (p) {
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        console.log(n.val);
        p = n.right;
    }
};

inOrder(tree);